/*
给定一个不含有重复值数组arr找到每一个i位置左边和右边离i位置最近且值比arr[i]小的位置。返回所有位置相应的信息。
arr = {3,4,1,5,6,2,7}
返回结果:{{-1,2},{0,2},{-1,-1},{2,5},{3,5},{2,-1},{5,-1}}
 */

/**
 *
 * @param {number[]} arr
 * @return {number[][]}
 */
function getNearLessNumPosition (arr) {
  const res = new Array(arr.length)
  const monoStack = [] // 单调栈，栈顶到底部单调递减
  for (let i = 0; i < arr.length; i++) {
    while (monoStack.length && arr[i] < arr[monoStack[monoStack.length - 1]]) {
      // 要加入的元素比栈顶小，要开始pop
      const index = monoStack.pop()
      res[index] = new Array(2)
      res[index][0] = monoStack.length ? monoStack[monoStack.length - 1] : -1
      res[index][1] = i
    }
    monoStack.push(i)
  }
  while (monoStack.length) {
    const index = monoStack.pop()
    res[index] = new Array(2)
    res[index][0] = monoStack.length ? monoStack[monoStack.length - 1] : -1
    res[index][1] = -1
  }
  return res
}

console.log(getNearPosition([3, 4, 1, 5, 6, 2, 7]))
